package leetcode.code1703;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	int[] sums;

	public int minMoves(int[] nums, int k) {
		int len = nums.length;
		sums = new int[len + 1];
		for (int i = 1; i <= len; i++) {
			sums[i] = sums[i - 1] + nums[i - 1];
		}
		// [1,0,0,1,0,1]
		int l = 0;
		while (l < len && nums[l] == 0) {
			l++;
		}
		int r = l;
		int ans = Integer.MAX_VALUE;
		while (r < len) {
			while (r < len && sums[r + 1] - sums[l] < k) {
				r++;
			}
			if (r < len && sums[r + 1] - sums[l] == k) {
				ans = Math.min(ans, f(nums, l, r, k, ans));
			}
			while (l <= r && l < len && nums[l] == 1) {
				l++;
			}
			while (l <= r && l < len && nums[l] == 0) {
				l++;
			}
		}
		return ans;
	}

	// 一段区间移动到一起的最小开销
	private int f(int[] nums, int l, int r, int k, int min) {
		int L = l, R = r;
		while (L < R && nums[L] == 1) {
			L++;
		}
		while (L < R && nums[R] == 1) {
			R--;
		}
		int M = 0;
		int half = k >> 1;
		int ans = 0;
		if (sums[L] - sums[l] >= half && ((k & 1) == 0 || nums[L] == 1)) {
			M = L;
			ans = this.moveRight(nums, M, r, min);
		} else if (((k & 1) == 0 && sums[r + 1] - sums[R] >= half)
				|| ((k & 1) == 1 && sums[r + 1] - sums[R] > half && nums[L] == 0)) {
			M = R;
			ans = this.moveLeft(nums, l, M, min);
		} else {
			if ((k & 1) == 0) {
				while (L <= R) {
					int mid = L + ((R - L) >> 1);
					if (sums[r + 1] - sums[mid] < half) {
						R = mid - 1;
					} else if (sums[r + 1] - sums[mid] > half) {
						L = mid + 1;
					} else {
						M = mid;
						break;
					}
				}
			} else {
				while (L <= R) {
					int mid = L + ((R - L) >> 1);
					if (nums[mid] == 1 && sums[r] - sums[mid] == half) {
						M = mid;
						break;
					} else if (sums[r + 1] - sums[mid] <= half) {
						R = mid - 1;
					} else if (sums[r + 1] - sums[mid] > half) {
						L = mid + 1;
					}
				}
			}
			ans = this.moveLeft(nums, l, M, min);
			if (ans >= min) {
				return min;
			}
			ans += this.moveRight(nums, M + 1, r, min);
			if (ans >= min) {
				return min;
			}
		}
		return ans;

	}

	// 右侧向目标M靠近
	private int moveRight(int[] nums, int M, int r, int min) {
		int L = M;
		int R = r;
		int ans = 0;
		// 1,0,0,1,0,1,1,1,1,0,1
		// 1,1,0,1,1,1,1,0,1
		// 1,1,1,1,1,1,0,1
		int zero = nums[M] == 0 ? 1 : 0;
		while (M < R) {
			if (nums[R] == 1) {
				while (R > L && nums[L] == 1) {
					L++;
				}
				ans += R - L;
				L++;
				if (ans >= min) {
					return min;
				}
			}
			R--;
		}
		return ans;
	}

	// 左侧向目标M靠近
	private int moveLeft(int nums[], int l, int M, int min) {
		int L = l;
		int R = M;
		int ans = 0;
		while (L < R) {
			if (nums[L] == 1) {
				while (R > L && nums[R] == 1) {
					R--;
				}
				ans += R - L;
				R--;
				if (ans >= min) {
					return min;
				}
			}
			L++;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(6, this.minMoves(HelpDebug.str2array3("[1,0,0,1,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,1,0,0,1]"), 5));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(10, this.minMoves(HelpDebug.str2array3("[1,1,0,0,0,0,0,1,1,1]"), 5));

	}

	public void debug5() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,0,0,1,0,0,1,0,1,1]"), 5));

	}

	public void debug6() {
		// TODO Auto-generated method stub
		HelpDebug.compare(0, this.minMoves(HelpDebug.str2array3("[1,1]"), 1));

	}

	public void debug7() {
		// TODO Auto-generated method stub
		HelpDebug.compare(1, this.minMoves(HelpDebug.str2array3("[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1]"), 14));

	}

	public void debug8() {
		// TODO Auto-generated method stub
		//[0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0]
		HelpDebug.compare(4, this.minMoves(HelpDebug.str2array3("[0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0]"), 7));

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug8();
		so.debug7();
		so.debug6();
		so.debug5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
